#include "mergesort.h"

// 构造函数：初始化 bars 和辅助数组 aux，同时预先收集所有 merge 步骤
MergeSort::MergeSort(const QVector<int> &values)
    : stepIndex(0), sorted(false), compareCount(0), swapCount(0) {

    // 将初始值包装为 SortBar 结构体，初始化为浅灰色
    for (int v : values) bars.append({v, Qt::lightGray});
    aux.resize(bars.size()); // 辅助数组等长，用于归并操作

    // 使用递归函数 collectSteps 来收集所有需要执行的 merge 区间
    std::function<void(int, int)> collectSteps = [&](int lo, int hi) {
        if (lo >= hi) return;  // 终止条件：单个元素无需归并
        int mid = (lo + hi) / 2;
        collectSteps(lo, mid);        // 左半边继续划分
        collectSteps(mid + 1, hi);    // 右半边继续划分
        steps.append({lo, hi});       // 记录归并区间
    };

    collectSteps(0, bars.size() - 1);  // 从整个数组开始收集归并步骤
}

// step：每次执行一步归并操作（对应 steps 中的一个 lo~hi 区间）
void MergeSort::step() {
    if (sorted || stepIndex >= steps.size()) {
        sorted = true;  // 若所有步骤已执行完，则标记排序完成
        return;
    }

    // 每次 step 前，重置所有颜色为默认浅灰
    for (auto &bar : bars) bar.color = Qt::lightGray;

    // 获取当前归并步骤区间
    auto [lo, hi] = steps[stepIndex++];
    int mid = (lo + hi) / 2;

    // 执行 merge 操作
    merge(lo, mid, hi);
}

// merge：对 bars[lo..mid] 和 bars[mid+1..hi] 进行归并
void MergeSort::merge(int lo, int mid, int hi) {
    // 复制需要归并的部分到辅助数组 aux
    for (int k = lo; k <= hi; ++k) {
        aux[k] = bars[k].value;
    }

    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; ++k) {
        if (i > mid) {
            bars[k].value = aux[j++];
        } else if (j > hi) {
            bars[k].value = aux[i++];
        } else {
            compareCount++;  // 记录比较次数

            // 按排序方式决定从左右子数组哪边取数据
            if ((sortOrder == SortOrder::Ascending && aux[j] < aux[i]) ||
                (sortOrder == SortOrder::Descending && aux[j] > aux[i])) {
                bars[k].value = aux[j++];
            } else {
                bars[k].value = aux[i++];
            }
        }

        // 给正在写入的位置加上颜色，表示被修改
        bars[k].color = Qt::cyan;
        swapCount++;  // 记录赋值次数
    }
}

// 判断是否所有归并步骤已完成
bool MergeSort::isFinished() const { return sorted; }

// 返回当前排序数据（带颜色）
const QVector<SortBar>& MergeSort::getData() const { return bars; }

// 返回并清空比较计数
int MergeSort::getAndResetCompareCount() {
    int c = compareCount;
    compareCount = 0;
    return c;
}

// 返回并清空交换（赋值）计数
int MergeSort::getAndResetSwapCount() {
    int s = swapCount;
    swapCount = 0;
    return s;
}

// 返回算法的时间/空间复杂度信息
QString MergeSort::getComplexityInfo() const {
    return "平均 O(n log n)，最好 O(n log n)，最坏 O(n log n)，空间复杂度 O(n)";
}

// 设置排序顺序（升序或降序）
void MergeSort::setOrder(SortOrder order) {
    sortOrder = order;
}
